package com.datastructure2.binarytree;

import com.sun.org.apache.xml.internal.utils.IntVector;
import sun.misc.LRUCache;
import sun.reflect.generics.tree.Tree;

import javax.lang.model.element.VariableElement;
import javax.swing.*;
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * @author: 临晖
 * @date: 2023/12/23
 * @description:
 */
public class Solution {

    ///**
    // * 二叉树前序遍历
    // * 方式一：递归之前序遍历
    // *
    // * @param root
    // * @return
    // */
    //public List<Integer> preorderTraversal(TreeNode root) {
    //    ArrayList<Integer> res = new ArrayList<>();
    //    preorder(root, res);
    //    return res;
    //}
    //
    //public void preorder(TreeNode curr, List<Integer> list) {
    //    if (curr == null) {
    //        return;
    //    }
    //
    //    list.add(curr.val);
    //
    //    preorder(curr.left, list);
    //    preorder(curr.right, list);
    //}
    //
    //
    ///**
    // * 二叉树遍历方式
    // * 方式一：递归之中序
    // *
    // * @param root
    // * @return
    // */
    //public List<Integer> inorderTraversal(TreeNode root) {
    //    LinkedList<Integer> res = new LinkedList<>();
    //    inorder(root, res);
    //
    //    return res;
    //}
    //
    //public void inorder(TreeNode curr, List<Integer> list) {
    //    if (curr == null) {
    //        return;
    //    }
    //
    //
    //    inorder(curr.left, list);
    //    list.add(curr.val);
    //    inorder(curr.right, list);
    //}
    //
    //
    ///**
    // * 二叉树得遍历方式
    // * 方式一：递归之后续遍历
    // *
    // * @param root
    // * @return
    // */
    //public List<Integer> postorderTraversal(TreeNode root) {
    //    LinkedList<Integer> res = new LinkedList<>();
    //    postorder(root, res);
    //
    //    return res;
    //}
    //
    //public void postorder(TreeNode curr, List<Integer> list) {
    //    if (curr == null) {
    //        return;
    //    }
    //
    //    postorder(curr.left, list);
    //    postorder(curr.right, list);
    //    list.add(curr.val);
    //}

    /**
     * 二叉树前序遍历
     * 方式二：迭代遍历
     * <p>
     * <p>
     * 中，左，右
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        stack.push(curr);

        //while (!stack.isEmpty()) {
        //    TreeNode node = stack.pop();
        //    res.add(node.val);                  //输出中间节点
        //    if (node.right != null) {           //右节点入栈
        //        stack.push(node.right);
        //    }
        //
        //    if (node.left != null) {        //左节点入栈
        //        stack.push(node.left);
        //    }
        //
        //}

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            res.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }


    /**
     * 二叉树遍历方式
     * 方式一：迭代中序遍历
     * 左中右
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;


        while (!stack.isEmpty() || curr != null) {

            if (curr != null) {
                //如果当前节点不等于空，那么一直向左走
                stack.push(curr);
                curr = curr.left;
            } else {
                //如果当前节点为空
                //输出当前节点
                curr = stack.pop();
                res.add(curr.val);
                //然后将当前节点移动到当前节点的右节点
                curr = curr.right;

            }
        }
        return res;
    }


    /**
     * 二叉树得遍历方式
     * 方式一：迭代后续遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        stack.push(curr);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);                  //输出中间节点
            if (node.left != null) {        //左节点入栈
                stack.push(node.left);
            }
            if (node.right != null) {           //右节点入栈
                stack.push(node.right);
            }
        }

        Collections.reverse(res);
        return res;
    }





    /**
     * 二叉树得遍历方式：通用迭代遍历
     *
     * @param root
     * @return
     */
    //public List<Integer> postorderTraversal(TreeNode root) {
    //    ArrayList<Integer> res = new ArrayList<>();
    //    Stack<TreeNode> stack = new Stack<>();
    //    if (root == null) {
    //        return res;
    //    }
    //
    //    stack.push(root);
    //
    //    while (!stack.isEmpty()) {
    //        TreeNode top = stack.peek();
    //        //前序遍历，中，左右
    //        if (top != null) {
    //            TreeNode temp = stack.pop();
    //            //放入中间节点
    //            stack.push(temp);
    //            stack.push(null);
    //
    //            //先放入右节点
    //            if (temp.right != null) {
    //                stack.push(temp.right);
    //            }
    //
    //            //放入左节点
    //            if (temp.left != null) {
    //                stack.push(temp.left);
    //            }
    //        } else {            //等于空得情况下，说明要弹出那个被标记得节点
    //            stack.pop();        //弹出空
    //            res.add(stack.pop().val);
    //        }
    //    }
    //
    //
    //    return res;
    //}
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<TreeNode> list = new LinkedList<>();

        if (root == null) {
            return res;
        }

        list.addLast(root);

        while (!list.isEmpty()) {
            int len = list.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while (len > 0) {
                len--;
                TreeNode first = list.getFirst();
                temp.add(first.val);

                if (first.left != null) {
                    list.addLast(first.left);
                }

                if (first.right != null) {
                    list.addLast(first.right);
                }

                list.removeFirst();
            }
            res.add(temp);
        }
        return res;
    }


    /**
     * 107. 二叉树的层序遍历 II
     * 中等
     * 759
     * 相关企业
     * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        //定义栈
        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.addLast(root);

        while (!queue.isEmpty()) {
            int len = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while (len > 0) {
                TreeNode node = queue.getFirst();

                if (node.left != null) {
                    queue.addLast(node.left);
                }

                if (node.right != null) {
                    queue.addLast(node.right);
                }
                temp.add(node.val);
                queue.removeFirst();
                len--;
            }

            res.add(temp);
        }

        //队列反转
        Collections.reverse(res);
        return res;
    }


    /**
     * 199. 二叉树的右视图
     * 中等
     * 1K
     * 相关企业
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.addLast(root);

        while (!queue.isEmpty()) {
            int len = queue.size();

            res.add(queue.getLast().val);

            while (len > 0) {
                //将当前节点取出来
                TreeNode node = queue.getFirst();

                if (node.left != null) {
                    queue.addLast(node.left);
                }

                if (node.right != null) {
                    queue.addLast(node.right);
                }

                queue.removeFirst();
                len--;
            }

        }

        return res;

    }


    /**
     * 637. 二叉树的层平均值
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            double count = len;
            long sum = 0;
            while (len > 0) {
                TreeNode temp = queue.getFirst();
                sum += temp.val;

                if (temp.left != null) {
                    queue.addLast(temp.left);
                }

                if (temp.right != null) {
                    queue.addLast(temp.right);
                }

                queue.removeFirst();
                len--;
            }

            res.add(new Double(sum / count));
        }
        return res;
    }


    /**
     * 429. N 叉树的层序遍历
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
     * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int len = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while (len > 0) {
                Node node = queue.getFirst();
                temp.add(node.val);

                if (node.children.size() != 0) {
                    queue.addAll(node.children);
                }

                queue.removeFirst();
                len--;
            }

            res.add(temp);
        }
        return res;
    }


    /**
     * 515. 在每个树行中找最大值
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
     *
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        //如果root为null，则直接返回res
        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.add(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            int max = Integer.MIN_VALUE;

            while (len > 0) {
                //获取当前节点
                TreeNode first = qu.getFirst();
                //和当前节点的值进行比较，看当前节点是否大于max
                max = Math.max(max, first.val);
                //加入下一层
                if (first.left != null) {
                    qu.addLast(first.left);
                }

                if (first.right != null) {
                    qu.addLast(first.right);
                }

                //移除当前节点
                qu.removeFirst();
                //当前层的节点数减一
                len--;
            }

            res.add(max);
        }


        return res;
    }


    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下
     *
     * @param root
     * @return
     */
    //public Node connect(Node root) {
    //    //如果根节点为空，那么直接结束
    //    if (root == null) {
    //        return null;
    //    }
    //    //创建队列
    //    LinkedList<Node> qu = new LinkedList<>();
    //    qu.add(root);
    //
    //    while (!qu.isEmpty()) {
    //        int len = qu.size();
    //
    //        while (len > 0) {
    //
    //            //获取当前层节点
    //            Node first = qu.removeFirst();
    //
    //
    //            if (len > 1) {
    //                first.next = qu.getFirst();
    //            }
    //
    //            //加入下一层节点
    //            if (first.left != null) {
    //                qu.addLast(first.left);
    //            }
    //
    //            if (first.right != null) {
    //                qu.addLast(first.right);
    //            }
    //
    //
    //            len--;
    //
    //        }
    //    }
    //
    //    return root;
    //}


    /**
     * 104. 二叉树的最大深度
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树 root ，返回其最大深度。
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     *
     * @param root
     * @return
     */
    //public int maxDepth(TreeNode root) {
    //    //思路一：广度优先，层序遍历
    //
    //    //if (root == null) {
    //    //    return 0;
    //    //}
    //    //
    //    //LinkedList<TreeNode> qu = new LinkedList<>();
    //    //qu.addLast(root);
    //    //
    //    //int maxDepth = 0;
    //    //
    //    //while (!qu.isEmpty()) {
    //    //    int len = qu.size();
    //    //    maxDepth++;
    //    //
    //    //    while (len > 0) {
    //    //        TreeNode node = qu.removeFirst();
    //    //
    //    //        if (node.left != null) {
    //    //            qu.addLast(node.left);
    //    //        }
    //    //
    //    //        if (node.right != null) {
    //    //            qu.addLast(node.right);
    //    //        }
    //    //
    //    //        len--;
    //    //    }
    //    //}
    //    //
    //    //return maxDepth;
    //
    //    //思路二，深度优先
    //
    //    if (root == null) {
    //        return 0;
    //    }
    //
    //    //左递归
    //    int leftDepth = maxDepth(root.left);    //左子树高度
    //    //右递归
    //    int rigthDepth = maxDepth(root.right);      //右子树的高度
    //    //中间逻辑
    //    return leftDepth > rigthDepth ? leftDepth + 1 : rigthDepth + 1;
    //    //所以是后序遍历
    //
    //}


    /**
     * 111. 二叉树的最小深度
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树，找出其最小深度。
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 说明：叶子节点是指没有子节点的节点
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {

        //思路一：广度优先，层序遍历
        //if(root == null) {
        //    return 0;
        //}
        //
        //LinkedList<TreeNode> qu = new LinkedList<>();
        //qu.addLast(root);
        //
        ////记录树的高度
        //int depth = 0;
        //
        //while (!qu.isEmpty()) {
        //    int len = qu.size();
        //    depth++;
        //
        //    while (len > 0) {
        //        TreeNode node = qu.removeFirst();
        //
        //        if (node.left == null && node.right == null) {
        //            return depth;
        //        }
        //
        //        if (node.left != null) {
        //            qu.addLast(node.left);
        //        }
        //
        //        if (node.right != null) {
        //            qu.addLast(node.right);
        //        }
        //
        //        len--;
        //    }
        //}
        //
        //return depth;

        //思路二：深度优先


        if (root == null) {
            return 0;
        }

        int leftDepth = minDepth(root.left);

        int rightDepth = minDepth(root.right);

        if (root.left == null && root.right != null) {
            return rightDepth + 1;
        }


        if (root.left != null && root.right == null) {
            return leftDepth + 1;
        }


        return Math.min(leftDepth, rightDepth) + 1;
    }


    /**
     * 226. 翻转二叉树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        //方式一：
        //if (root == null) {
        //    return null;
        //}
        //
        //
        //
        //invertTree(root.left);
        //invertTree(root.right);
        //
        ////如果不为空
        //swap(root);
        //
        //return root;

        //方式二
        if (root == null) {
            return null;
        }

        //前序遍历，中左右

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            //弹出当前中间节点
            TreeNode node = stack.pop();
            //将当前节点加入到res中
            swap(node);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return root;

    }

    public void swap(TreeNode root) {
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;
    }


    /**
     * 101. 对称二叉树
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {

        if (root == null) {
            return true;
        }

        return compare(root.left, root.right);


    }

    /**
     * 判断俩棵树是否相等
     *
     * @param left
     * @param right
     * @return
     */
    public boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }

        if (left == null || right == null) {
            return false;
        }

        //不等于继续往下判断
        if (left.val != right.val) {
            return false;
        }

        return compare(left.left, right.right) && compare(left.right, right.left);
    }


    /**
     * 100. 相同的树
     * 简单
     * 相关标签
     * 相关企业
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }

        if (p == null || q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }


    /**
     * 572. 另一棵树的子树
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     *
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //思路，不断判断每个节点
        if (root == null && subRoot != null) {
            return false;
        }

        if (root != null && subRoot == null) {
            return true;
        }

        //boolean res = false;
        //Stack<TreeNode> stack = new Stack<>();
        //stack.push(root);
        //
        //while (!stack.isEmpty()) {
        //    TreeNode node = stack.pop();
        //
        //    //加入，核心逻辑
        //    res = isSameTree(node, subRoot);
        //
        //    if (res) {
        //        return res;
        //    }
        //
        //    if (node.right != null) {
        //        stack.push(node.right);
        //    }
        //
        //    if (node.left != null) {
        //        stack.push(node.left);
        //    }
        //}
        //return res;

        //以上代码可以更换为以下代码，牛！！！！！！！！！！

        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }


    /**
     * 代码
     * 测试用例
     * 测试结果
     * 测试结果
     * 222. 完全二叉树的节点个数
     * 简单
     * 相关标签
     * 相关企业
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        //思路一：遍历遍历
        //if (root == null) {
        //    return 0;
        //}
        //
        ////左子树的节点数
        //int left = countNodes(root.left);
        //
        //int right = countNodes(root.right);
        //
        //return left + right + 1;

        //思路二，层序遍历

        if (root == null) {
            return 0;
        }


        LinkedList<TreeNode> qu = new LinkedList<>();
        int sum = 0;

        qu.addLast(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            sum += len;
            while (len > 0) {
                TreeNode node = qu.removeFirst();

                if (node.left != null) {
                    qu.addLast(node.left);
                }

                if (node.right != null) {
                    qu.addLast(node.right);
                }

                len--;
            }
        }

        return sum;
    }


    /**
     * 110. 平衡二叉树
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {

        if (root == null) {
            return true;
        }

        int res = getDepth(root);
        if (res == -1) {
            return false;
        }

        return true;
    }


    public int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }


        //左子树的高度
        int left = getDepth(root.left);
        //右子树的高度
        int right = getDepth(root.right);

        if (Math.abs(left - right) > 1) {
            return -1;
        }

        if (left == -1 || right == -1) {
            return -1;
        }

        return left > right ? left + 1 : right + 1;
    }


    /**
     * 559. N 叉树的最大深度
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个 N 叉树，找到其最大深度。
     * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
     * N 叉树输入
     *
     * @param root
     * @return
     */
    public int maxDepth(Node root) {
        //方式一：层序遍历
        //if (root == null) {
        //    return 0;
        //}
        //
        //LinkedList<Node> qu = new LinkedList<>();
        //int depth = 0;
        //qu.addLast(root);
        //
        //while (!qu.isEmpty()) {
        //    int len = qu.size();
        //
        //    while (len > 0) {
        //        Node node = qu.removeFirst();
        //
        //        if (node.children.size() != 0) {
        //            qu.addAll(node.children);
        //        }
        //
        //
        //        len--;
        //    }
        //    depth++;
        //}
        //
        //return depth;


        if (root == null) {
            return 0;
        }

        ArrayList<Integer> res = new ArrayList<>();

        for (int i = 0; i < root.children.size(); i++) {
            res.add(maxDepth(root.children.get(i)));
        }

        if (res.size() == 0) {
            return 1;
        } else {
            return Collections.max(res) + 1;
        }

    }


    /**
     * 257. 二叉树的所有路径
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
     * 叶子节点 是指没有子节点的节点。
     * <p>
     * 前序遍历：中，左，右
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        String path = "";

        pry(root, res, root.val + "");

        return res;
    }


    public void pry(TreeNode node, List<String> res, String path) {


        if (node.left == null && node.right == null) {

            res.add(path);
            return;
        }


        //左节点
        if (node.left != null) {

            pry(node.left, res, path + "->" + node.left.val);
            //回溯

        }

        //右节点
        if (node.right != null) {

            pry(node.right, res, path + "->" + node.right.val);
            //回溯

        }

    }


    /**
     * 404. 左叶子之和
     * 简单
     * 相关标签
     * 相关企业
     * 给定二叉树的根节点 root ，返回所有左叶子之和
     * <p>
     * 思路：
     * 确认遍历顺序：中序
     * 什么时候结束递归？碰到左子叶，子叶？即没有孩子节点
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return 0;
        }
        int sum = getLeftSum(root);
        //LinkedList<TreeNode> qu = new LinkedList<>();
        //
        //qu.addLast(root);
        //
        //while (!qu.isEmpty()) {
        //    int size = qu.size();
        //
        //    while (size > 0) {
        //        TreeNode node = qu.removeFirst();
        //
        //        if(node.left != null) {
        //            qu.addLast(node.left);
        //            if (node.left.left == null && node.left.right == null) {
        //                sum += node.left.val;
        //            }
        //        }
        //
        //        if (node.right != null) {
        //            qu.addLast(node.right);
        //        }
        //
        //        size--;
        //    }
        //}

        return sum;
    }

    public int getLeftSum(TreeNode node) {

        //退出条件，中心逻辑
        //满足条件：如何能确定返回右子树的左子叶值？
        if (node == null) {
            return 0;
        }


        //左
        int left = getLeftSum(node.left);


        if (node.left != null && node.left.left == null && node.left.right == null) {
            left = node.left.val;
        }

        //右
        int right = getLeftSum(node.right);


        return left + right;


    }


    /**
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = 0;
        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.addLast(root);

        while (!qu.isEmpty()) {
            int size = qu.size();
            int temp = size;
            while (size > 0) {
                TreeNode node = qu.removeFirst();

                if (temp == size && node.left == null && node.right == null) {
                    sum = node.val;
                }

                if (node.left != null) {
                    qu.addLast(node.left);
                    //if (node.left.left == null && node.left.right == null) {
                    //    sum = node.left.val;
                    //}
                }

                if (node.right != null) {
                    qu.addLast(node.right);
                }

                size--;
            }
        }

        return sum;
    }


    /**
     * 112. 路径总和
     * 简单
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return hashPath(root, targetSum, 0);
    }

    public boolean hashPath(TreeNode node, int targetSum, int sum) {
        sum += node.val;

        //定义返回条件
        if (node.left == null && node.right == null) {
            return sum == targetSum;
        }


        boolean left = false;

        if (node.left != null) {
            left = hashPath(node.left, targetSum, sum);
        }

        boolean right = false;

        if (node.right != null) {
            right = hashPath(node.right, targetSum, sum);
        }


        return left || right;
    }


    /**
     * 113. 路径总和 II
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        path(root, targetSum, res, new ArrayList<>());
        return res;
    }

    public void path(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {

        path.add(root.val);

        if (root.left == null && root.right == null) {
            int sum = 0;
            for (int x : path) {
                sum += x;
            }

            if (sum == targetSum) {
                res.add(new ArrayList<>(path));
            }
            return;
        }

        if (root.left != null) {
            path(root.left, targetSum, res, path);
            //回溯
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path(root.right, targetSum, res, path);
            //回溯
            path.remove(path.size() - 1);
        }

    }


    /**
     *
     * 106. 从中序与后序遍历序列构造二叉树  中；左中右  后序：左右中
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     *
     * @param inorder
     * @param postorder
     * @return
     */
    //public TreeNode buildTree(int[] inorder, int[] postorder) {
    //    //第一步，如果数组大小为零的话，那么返回null
    //    if (postorder.length == 0) {
    //        return null;
    //    }
    //
    //    //取后续数组的最后一个元素：中
    //    int in = postorder[postorder.length - 1];
    //    TreeNode root = new TreeNode(in);
    //
    //    //叶子节点
    //    if (postorder.length == 1) {
    //        return root;
    //    }
    //
    //    int inIndex = 0;
    //    for (; inIndex < inorder.length; inIndex++) {
    //        if (inorder[inIndex] == in) {
    //            break;
    //        }
    //    }
    //
    //    //切割，出来左子树和右子树
    //    int[] leftInorder = Arrays.copyOfRange(inorder, 0, inIndex);
    //    int[] rightInorder = Arrays.copyOfRange(inorder, inIndex + 1, inorder.length);
    //
    //    //
    //    int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
    //    int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length - 1);
    //
    //    TreeNode leftNode = buildTree(leftInorder, leftPostorder);
    //    TreeNode rightNode = buildTree(rightInorder, rightPostorder);
    //
    //    root.left = leftNode;
    //    root.right = rightNode;
    //
    //    return root;
    //}


    /**
     * 105. 从前序与中序遍历序列构造二叉树 中左右 左中右
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //思路：依据前序遍历，先找到中间结点，然后通过中间结点切割后续遍历
        //第一：如果前序遍历数组元素数量为0，那么，无需继续切割
        if (preorder.length == 0) {
            return null;
        }

        //第二步，从前序遍历中找到中间节点
        int nodeVal = preorder[0];
        TreeNode root = new TreeNode(nodeVal);

        //如果，前序数组中只有一个元素，那么不需要继续切割了
        if (preorder.length == 1) {
            return root;
        }

        //第三，通过中间节点，切割中序遍历素组 :左中右
        int rootIndex = 0;
        for (; rootIndex < inorder.length; rootIndex++) {
            if (inorder[rootIndex] == nodeVal) {
                break;
            }
        }

        //找到后
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
        //然后再通过中序遍历的左右树切割前序的，方式：左右子树的顺序虽然不同，但是，节点个数一定是相同的

        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftInorder.length);
        int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftInorder.length, preorder.length);

        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;
    }


    /**
     * 654. 最大二叉树
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
     * 创建一个根节点，其值为 nums 中的最大值。
     * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
     * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
     * 返回 nums 构建的 最大二叉树 。
     *
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) {
            return null;
        }

        int maxIndex = 0;

        //找到最大数
        for (int i = 1; i < nums.length; i++) {
            if (nums[maxIndex] < nums[i]) {
                maxIndex = i;
            }
        }

        TreeNode root = new TreeNode(nums[maxIndex]);

        if (nums.length == 1) {
            return root;
        }

        //否则，分割出左右子树
        int[] leftTree = Arrays.copyOfRange(nums, 0, maxIndex);
        int[] rightTree = Arrays.copyOfRange(nums, maxIndex + 1, nums.length);

        root.left = constructMaximumBinaryTree(leftTree);
        root.right = constructMaximumBinaryTree(rightTree);

        return root;


    }


    /**
     * 617. 合并二叉树
     * 简单
     * 相关标签
     * 相关企业
     * 给你两棵二叉树： root1 和 root2 。
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     * 返回合并后的二叉树。
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if (root1 == null && root2 == null) {
            return null;
        }


        if (root1 == null) {
            return root2;
        }

        if (root2 == null) {
            return root1;
        }


        int nodeVal = root1.val + root2.val;
        TreeNode root = new TreeNode(nodeVal);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);

        return root;

    }


    /**
     * 700. 二叉搜索树中的搜索
     * 简单
     * 相关标签
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }

        if (root.val < val) {  //去右子树
            return searchBST(root.right, val);
        } else if (root.val > val) {  //去左子树
            return searchBST(root.left, val);
        }

        return root;

    }


    /**
     * 98. 验证二叉搜索树
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效 二叉搜索树定义如下：
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * <p>
     * 左中右
     *
     * @param root
     * @return
     */

    //public boolean isValidBST(TreeNode root) {
    //    if (root == null) {
    //        return true;
    //    }
    //
    //    boolean left = isValidBST(root.left);
    //
    //    if (!left) {
    //        return false;
    //    }
    //
    //    if (pre != null) {
    //        if (pre.val >= root.val) {
    //            return false;
    //        }
    //    }
    //
    //    pre = root;
    //
    //    return isValidBST(root.right);
    //
    //
    //}


    //if (root == null) {
    //  return;
    //}
    //
    //xxx(root.left);
    //System.out.println(root.val);
    //xxx(root.right);


    /**
     * 501. 二叉搜索树中的众数
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
     * <p>
     * 如果树中有不止一个众数，可以按 任意顺序 返回。
     * <p>
     * 假定 BST 满足如下定义：
     * <p>
     * 结点左子树中所含节点的值 小于等于 当前节点的值
     * 结点右子树中所含节点的值 大于等于 当前节点的值
     * 左子树和右子树都是二叉搜索树
     * <p>
     * <p>
     * 思路：二叉搜索树：中序遍历，是一个排好的是有顺序的递增数组，所以可以用递归双指针
     *
     * @param root
     * @return
     */


    //int max = 0;        //如果小于max，不需要管，如果等于max，加入，如果大于max，清除全部，然后加入
    //int count = 0;
    //ArrayList<Integer> list = new ArrayList<>();
    //
    //public int[] findMode(TreeNode root) {
    //    find(root);
    //
    //
    //    int[] res = new int[list.size()];
    //    for (int i = 0; i < res.length; i++) {
    //        res[i] = list.get(i);
    //    }
    //
    //
    //    return res;
    //
    //}

    //public void find(TreeNode root) {
    //    if (root == null) {
    //        return;
    //    }
    //
    //    //左
    //    findMode(root.left);
    //
    //
    //    //中
    //    if (pre == null) {      //上一个节点为空
    //        count = 1;
    //    } else if (pre.val == root.val) {       //上一个节点不为空，那么当前节点的值和上一个节点的值进行比较
    //        count++;
    //    } else if (pre.val != root.val) {
    //        count = 1;
    //    }
    //
    //
    //    pre = root;
    //
    //    if (count == max) {
    //        list.add(root.val);
    //    }
    //
    //    if (count > max) {
    //        list.clear();
    //        list.add(root.val);
    //        max = count;
    //    }
    //
    //
    //    //右
    //    findMode(root.right);
    //}


    /**
     * 236. 二叉树的最近公共祖先
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if ((root.val >= p.val && root.val <= q.val) || (root.val >= q.val && root.val <= p.val)) {
            return root;
        }

        if (root.val > q.val && root.val > p.val) {     //因为不确定p和q哪个大，所以选择都大于
            return lowestCommonAncestor(root.left, p, q);
        }

        if (root.val < p.val && root.val < q.val) {     //同理。因为不确定p和q哪个小，所以选择都小于
            return lowestCommonAncestor(root.right, p, q);
        }

        return null;
    }


    /**
     * 701. 二叉搜索树中的插入操作
     * 中等
     * 相关标签
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
     * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }

        if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        }

        return root;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
     * 一般来说，删除节点可分为两个步骤：
     * 首先找到需要删除的节点；
     * 如果找到了，删除它。
     *
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root == null) {
            return root;
        }


        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            //有俩个子节点
            if (root.left != null && root.right != null) {
                TreeNode node = root.right;

                while (node.left != null) {
                    node = node.left;
                }

                node.left = root.left;

                return root.right;
            }

            //有一个子节点(左/右)
            else if (root.left != null) {
                return root.left;
            } else if (root.right != null) {
                return root.right;
            }

            //没有子节点
            return null;
        }


        return root;

    }


    /**
     * 669. 修剪二叉搜索树
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }


        root.left = trimBST(root.left, low, high);

        root.right = trimBST(root.right, low, high);
        if (root.val < low || root.val > high) {
            //有俩个子节点
            if (root.left != null && root.right != null) {
                TreeNode node = root.right;

                while (node.left != null) {
                    node = node.left;
                }

                node.left = root.left;

                return root.right;
            }

            //有一个子节点(左/右)
            else if (root.left != null) {
                return root.left;
            } else if (root.right != null) {
                return root.right;
            }

            //没有子节点
            return null;
        }

        return root;
    }


    /**
     * 108. 将有序数组转换为二叉搜索树
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }

        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }

        //找根节点
        int minIndex = nums.length / 2;
        TreeNode root = new TreeNode(nums[minIndex]);

        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, minIndex));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, minIndex + 1, nums.length - 1));

        return root;
    }


    /**
     * 538. 把二叉搜索树转换为累加树
     * 中等
     * 相关标签
     * 相关企业
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之
     * <p>
     * 规律：右，中，左
     *
     * @param root
     * @return
     */
    int pre = 0;
    public TreeNode convertBST(TreeNode root) {
        bst(root);
        return root;
    }

    public void bst(TreeNode root) {
        if (root == null) {
            return;
        }

        bst(root.right);

        root.val += pre;
        pre = root.val;

        bst(root.left);
    }


}

